package com.fantaike.algorithm.heap;

import javafx.scene.control.Skin;

/**
 * 堆排序
 * @author jishushen
 * @create 2022-06-25 16:14
 */
public class HeapSort {
    //判断堆中索引处的元素是否小于索引j处的元素
    private static boolean less(Comparable[] heap,int i,int j){
        return heap[i].compareTo(heap[j]) < 0;
    }
    //交换堆中索引i处和j处的值
    private static void exch(Comparable[] heap,int i,int j){
        Comparable tmp = heap[i];
        heap[i] = heap[j];
        heap[j] = tmp;
    }
    //根据原数组source构建成堆heap
    private static void createHeap(Comparable[] source,Comparable[] heap){
        //把source中元素拷贝到heap中，heap中的元素形成一个无序的堆
        System.arraycopy(source,0,heap,1,source.length);
        //对堆中的元素做下沉调整（从长度的一半处开始，往索引1处扫描）
        for (int i=(heap.length)/2;i>0;i--){
            sink(heap,i,heap.length - 1);
        }
    }


    /**
     * 对source数组中的数据从小到大排序
     * 1.对构造好的堆，我们只需要做删除操作，就可以完成排序
     * 2.将堆顶元素和堆中最后一个元素交换位置
     * 3.通过对堆顶元素下沉调整堆，把最大的元素放到堆顶（此时最后一个元素不参数调整，因为最大的数据已经到了数组最左边）
     * 4.重复1-2步骤直到堆中剩最后一个元素
     * @Date: 2022/7/2 15:45
     * @Author: xuepeng
     * @Return
     * @Throws
     */
    public static void sort(Comparable[] source){
        //构造堆
        Comparable[] heap = new Comparable[source.length + 1];
        createHeap(source,heap);
        //定义一个变量，记录未排序的元素中最大的索引
        int N = heap.length - 1;
        //通过循环交换1索引处的元素和排序的元素中最大的索引处的元素
        while (N!=1){
            //交换元素
            exch(heap,1,N);
            //排序交换后最大元素所在的索引，让其不参与堆的下沉操作
            N--;
            //需要对索引1处的元素做下沉调整
            sink(heap,1,N);
        }
        //把heap中的元素复制到原数组source中
        System.arraycopy(heap,1,source,0,source.length);
    }

    //在heap堆中，对target处的元素做下沉，范围是0-range
    private static void sink(Comparable[] heap,int target,int range){
        //通过循环不断比较当前target节点和其左节点2*target及右节点2*target+1处的较大值的元素大小，如果当前节点小则要交换位置
        while (2*target<=range){
            //获取当前节点中较大的子节点
            int max;//记录较大节点的索引
            if (2*target+1<=range){
                //找到最大索引
                max = less(heap,2*target,2*target+1) ? 2*target+1 : 2*target;
            }else {
                max = 2*target;
            }
            //2.比较当前节点的值和较大节点时
            if (less(heap,max,target)){
                break;
            }
            exch(heap,target,max);
            //重新赋值
            target = max;
        }
    }
}
